#include "../include/constants.h"
#include "../include/binsrchtree.h"
#include "../include/errors.h"
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/*
BST: binary search tree
FD: file descriptor
*/

/*
Function Name: bst_display(...)
Descriptions: display nodes in the BST by the node's key.
Parameters: BST or BST node.
Return Type: void.
*/
void bst_display(b_node* tree)
{
    static int i=0;
    if(tree!=NULL)
    {
#if BST_DEBUG
        printf("tree -%s-%s-%s-\n",tree->fileDes->f_path,tree->fileDes->f_name,tree->fileDes->f_type);
#endif
        printf("%s\n\n",tree->key);
#if BST_DEBUG
        printf("LEFT\n");
#endif
        bst_display(tree->left);
#if BST_DEBUG
        printf("RIGHT\n");
#endif
        bst_display(tree->right);
    }
}

/*
Function Name: getdesc(...)
Descriptions: generates a FD. Used to generate FDs to test BST functionality.
Parameters: FD values
Return Type: pointer to FD: fdesc*.
*/
fdesc* getdesc(char dir[],char file[], char type[])
{
    fdesc* ins;
    ins=(fdesc*)malloc(sizeof(fdesc));
    strcpy(ins->f_name,file);
    strcpy(ins->f_path,dir);
    strcpy(ins->f_type,type);
    return ins;
}

/*
Function Name: edit_fd(...)
Descriptions: Generate a node of BST type from a FD.
Parameters: FD
Return Type: pointer to BST node : b_node*
*/
b_node* edit_fd(fdesc *fd)
{
    b_node* ins=(b_node*)malloc(sizeof(b_node));
    ins->fileDes=fd;
    ins->key=(char*)malloc(sizeof(char)*CHARSIZE);
    ins->left=NULL;
    ins->right=NULL;
    ins->parent=NULL;
    return ins;

}

/*
Function Name: bst_search_fd(...)
Descriptions: Search the BST wrt a key 'find' here.
Parameters: BST and the key to be searched.
Return Type: returns a pointer to FD if the key is found else NULL.
*/
fdesc* bst_search_fd(b_node* tree, char* find)
{
#if BST_DEBUG
    printf("inp -%s-\n",find);
#endif
    b_node* temp;
    temp=bst_search(tree,find);
    if(temp==NULL)
        return NULL;
    return temp->fileDes;
}

/*
Function Name: bst_search(...)
Descriptions: Search the BST wrt a key 'find' here.
Parameters: BST and the key to be searched.
Return Type: returns a BST node pointer if the key is found else NULL.
*/
b_node* bst_search(b_node* tree, char * find)
{

    char  ch[CHARSIZE], tr[CHARSIZE];
    char *try;
    try=(char*)malloc(sizeof(char)*256);
    if(tree==NULL)
        return NULL;
    if(strcmp(tree->key,find)==0)
        return tree;
    else if(strcmp(find,tree->key)<0)
    {
#if BST_DEBUG
        printf("bst_srch left %s\n",tree->fileDes->f_path);
#endif
        return bst_search(tree->left,find);
    }
    else if(strcmp(find,tree->key)>0)
    {
#if BST_DEBUG
        printf("bst_srch right %s\n",tree->fileDes->f_path);
#endif
        return bst_search(tree->right,find);
    }

}

/*
Function Name: gen_key(...)
Descriptions: generate key of the BST node using a FD.
Parameters: The memory allocated for the key to be generated and the
     corresponding FD whose key has to be generated.
Return Type: void
*/
void gen_key(char* gen, fdesc* gen_fd)
{
    strcpy(gen,gen_fd->f_path);
#if BST_DEBUG
    printf("-%s-%d- \n",gen_fd->f_path,strlen(gen_fd->f_path));
#endif
    if(gen_fd->f_path[strlen(gen_fd->f_path)-1]!='/')
        strcat(gen,"/");
    strcat(gen,gen_fd->f_name);
    /*if(strcmp(gen_fd->f_name,"/")!=0)
       strcat(gen,"/");*/
}

/*
Function Name: init_bst(...)
Descriptions: initialize a BST.
Parameters: allocated BST root/node and FD of root of BST.
Return Type: int: Successful/Unsuccessful.
*/
int init_bst(b_node* tree, fdesc* inp)
{
    char *try;
    try=(char*)malloc(sizeof(char)*CHARSIZE);
    if((strcmp(inp->f_name,"/")==0) && (strcmp(inp->f_path,"")==0))
    {
        (tree)->fileDes=inp;
        strcpy(try,inp->f_path);
        strcat(try,inp->f_name);
        strcpy((tree)->key,try);
        (tree)->left=NULL;
        (tree)->right=NULL;
        (tree)->parent=NULL;
        return 1;/*SUCCESSFUL*/
    }
    else return 0;/*UNSUCCESSFUL*/
}

/*
Function Name: bst_insert(...)
Descriptions: insert nodes of type BST node in BST using FD.
Parameters: BST root and FD to be inserted.
Return Type: int: successful/unsuccessful/invalid.
*/
int bst_insert(b_node* tree, fdesc* inp)
{
#if BST_DEBUG
    printf("IN BST     insert  -%s-%s-%s-\n",(tree)->fileDes->f_path,(tree)->fileDes->f_name,(tree)->fileDes->f_type);
    printf("inp BST -%s-%s-%s-%ld-%ld\n",inp->f_path,inp->f_name,inp->f_type,inp->f_size,inp->block_number);
#endif
    b_node* ins=NULL;
    ins= edit_fd(inp);
    char pr[CHARSIZE], cu[CHARSIZE], tr[CHARSIZE],in[CHARSIZE];
    strcpy(tr,tree->key);
#if BST_DEBUG
    printf("%s PRINT TR\n",tr);
#endif
    if(strcmp(inp->f_path,"")==0 && strcmp(inp->f_name,"/")==0)
        return -1;
    gen_key(in,ins->fileDes);
    strcpy(ins->key,in);
#if BST_DEBUG
    printf("%s PRINT IN\n",in);
#endif

    if(strcmp(ins->fileDes->f_name,"")!=0)
    {
        b_node* prev=NULL;
        b_node* curr=(tree);
        strcpy(pr,"");
        strcpy(cu,tr);
        while((curr)!=NULL)
        {
            prev=curr;
            strcpy(pr,cu);
            if(strcmp(curr->fileDes->f_name,tree->fileDes->f_name)!=0)
            {
                gen_key(cu,curr->fileDes);
                strcpy((curr)->key,cu);
            }
#if BST_DEBUG
            printf("%s PRINT CU\n",cu);
#endif
            if(strcmp(ins->key,(curr)->key)<0)
            {
                (curr)=(curr)->left;
            }
            else if(strcmp(ins->key,(curr)->key)>0)
            {
                (curr)=(curr)->right;
            }
            else
            {
#if BST_DEBUG
                printf("element already exists\n");
#endif
                return 0;/*unsuccessful*/
            }
        }
        ins->parent=(prev);
        if(prev==NULL)
            (tree)=ins;
        else if(strcmp(ins->key,(prev)->key)==0)
        {
#if BST_DEBUG
            printf("%s element already exists\n",ins->key);
#endif
            return 0;/*UNSUCCESSFUL;*/
        }
        else if (strcmp(ins->key,(prev)->key)<0)
        {
            (prev)->left=ins;
        }
        else
        {
            (prev)->right=ins;
        }
    }
    else
    {
#if BST_DEBUG
        printf("invalid input\n");
#endif
        return -1; /*invalid*/
    }
    return 1;/*SUCCESSFUL;*/
}

/*
Function Name: transplant(...)
Descriptions: remove a node from the BST
Parameters: BST root, node to be eliminated and the predecessor of the node
     to be eliminated.
Return Type: void.
*/
void transplant(b_node* tree,b_node* u, b_node* v)
{
    if(u->parent==NULL)
        (tree)=v;
    else if(u==u->parent->left)
        u->parent->left=v;
    else u->parent->right=v;
    if(v!=NULL)
        v->parent=u->parent;

}

/*
Function Name: tree_min(...)
Descriptions: obtain predecessor of the node
Parameters: BST node.
Return Type: pointer to predecessor.
*/
b_node* tree_min(b_node* val)
{
    while(val->left!=NULL)
        val=val->left;
    return val;
}

/*
Function Name: bst_remove(...)
Descriptions: delete a node from BST
Parameters: BST root and FD whose node has to be removed if present.
Return Type: int: succcessful/unsuccessful
*/
int bst_remove(b_node* tree,fdesc* rem)
{
    if(tree==NULL)
        return UNSUCCESSFUL;
    else
    {
        char *fin_key;
        fin_key=(char*)malloc(sizeof(char)*CHARSIZE);
        b_node* elim;
        gen_key(fin_key,rem);

        elim=bst_search((tree),fin_key);
        if(elim==NULL)
        {
          

            printf("not present\n");

            return 0;
        }
        else
        {
            bst_rem(tree,elim);
       

            return 1;
        }
    }
}

/*
Function Name: bst_rem(...)
Descriptions: remove a BST node from BST root/tree
Parameters: BST root and BST node.
Return Type: void
*/
void bst_rem(b_node* tree, b_node* elim)
{
    b_node * pred;
    if(elim->left==NULL)
        transplant(tree,elim,elim->right);
    else if(elim->right==NULL)
        transplant(tree,elim,elim->left);
    else
    {
        pred=tree_min(elim->right);
        if(pred->parent!=elim)
        {
            transplant(tree,pred,pred->right);
            pred->right=elim->right;
            pred->right->parent=pred;
        }
        transplant(tree,elim,pred);
        pred->left=elim->left;
        pred->left->parent=pred;
    }
    return;
}


/*
Function Name: bst_empty(...)
Descriptions: reinitialize BST
Parameters: BST root
Return Type: int: successful/unsuccessful
*/
int bst_empty(b_node *tree)
{
    if(empty(tree))
    {
        tree=NULL;
        return 1;
    }
    return 0;
}

/*
Function Name: empty(...)
Descriptions: recursively delete BST nodes
Parameters: BST root.
Return Type: int
*/
int empty(b_node * tree)
{
    if(tree!=NULL)
    {
#if BST_DEBUG
        printf("LEFT\n");
#endif
        empty(tree->left);
#if BST_DEBUG
        printf("RIGHT\n");
#endif
        empty(tree->right);
        tree->left=NULL;
        tree->right=NULL;
        free(tree);
        tree=NULL;
        return 1;
    }
    else return 0;
}



